#include <bits/stdc++.h>
using namespace std;

int n, m, a[50], ans = 0;

vector<int> zuo, you;

void dfs1(int step, int sum) {
  if (step == n / 2 + 1) {
    zuo.push_back(sum);
    return;
  }
  dfs1(step + 1, (sum + a[step]) % m);
  dfs1(step + 1, sum % m);
}

void dfs2(int step, int sum) {
  if (step == n + 1) {
    you.push_back(sum);
    return;
  }
  dfs2(step + 1, (sum + a[step]) % m);
  dfs2(step + 1, sum % m);
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] %= m;
  }
  dfs1(1, 0);
  dfs2(n / 2 + 1, 0);

  /*
    sort(you.begin(), you.end());
  for (int i = 0; i < zuo.size(); i++) {
    int j = lower_bound(you.begin(), you.end(), m - zuo[i]) - you.begin();
    j--;
    ans = max(ans, (zuo[i] + you[j]) % m);
  }
  cout << ans << endl;
  */

  sort(zuo.begin(), zuo.end());
  sort(you.begin(), you.end());
  int l = 0;
  int r = you.size() - 1;
  while (l < zuo.size() && r >= 0) {
    if (zuo[l] + you[r] >= m) {
      r--;
    } else {
      ans = max(ans, zuo[l] + you[r]);
      l++;
    }
  }
  cout << ans;
  return 0;
}
